МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Кафедра ЕОМ Застосування генетичних алгоритмів для вирішення задачі комівояжера Методичні вказівки до лабораторної роботи № 3 з курсу: “Системи штучного інтелекту” для студентів Затверджено на засіданні кафедри “Електронних обчислювальних машин” Протокол № Від 2003 р. Львів 2003 Застосування генетичних алгоритмів для вирішення задачі комівояжера. Методичні вказівки до лабораторної роботи № 3 з курсу: “Системи штучного інтелекту” для студентів , 12 с. Укладач: Ємець В.Ф., професор, д.т.н. Сокіл В.М., асистент Юрчак І.Ю, доцент, к.т.н. Відповідальний за випуск: Кремінь В.Т., ст. викладач кафедри ЕОМ Рецензенти: Березко Л.О., доцент кафедри ЕОМ, к.т.н. Каркульовський В.І., доцент кафедри АСУ, к.т.н. 1. Мета роботи Створення програми, на основі генетичних алгоритмів для вирішення задачі комівояжера. 2. Теоретичні відомості В природі існує багато процесів, які шукають стабільні стани. Такі процеси можуть бути трактовані як природні оптимізаційні процеси. В останні тридцять років зроблено декілька проб, для розвитку оптимізаційних алгоритмів, що імітують природні оптимізаційні алгоритми. Такі спроби найефективніше втілені у наступних методах: Алгоритм відпалу металу (Simulated Annealling), що базується на процесі відпалу, запозичений з металургії Штучні нейронні мережі, що базуються на процесах, запозичених з роботи нервових клітин Еволюційні алгоритми, що базуються на біологічних еволюційних процесах Алгоритми, що моделюють еволюційні процеси носять назву еволюційних алгоритмів, і можуть бути поділені на декілька класів: Генетичні алгоритми(Holland 1975), Еволюційне програмування (Fogel 1962), Еволюційна стратегія (Bremermann 1965), Генетичне програмування(Koza 1992) Інші оптимізаційні алгоритми, що базуються на еволюційній теорії Дарвіна про походження видів Генетичні алгоритми Еволюційні алгоритми є дослідними алгоритмами, що імітують природні еволюційні процеси. Їхне застосування для розв”язання комбінаторно-оптимізаційних проблем є найпопулярнішою темою для наукових задач. В останній час було опубліковано багато праць та книжок на тему застосування еволюційних методів зостосування в різноманітних ділянках науки, таких як біологія, хімія, комп”ютерне проектування, криптографія, медицина, мікроелектроніка, розпізнавання образів, планування виробництва, робототехніка, телекомунікації та інших. Голанд (1975) розробив методику генетичних алгоритмів. В цих алгоритмах простір пошуків розв”язання проблеми є представлення як відбір особин. Таки особини проедставлені як набір знаків (або групами знаків), і часто називаються хромосомами. Метою використання генетичного алгоритму є знаходження особини з пошуком простору, яка представляє найкращий “генетичний матеріал”. Якості одиночної особини оцінюються за функцією пристосованя. Частина простору пошуків, яка є протестованою, називається популяцією. Переважно генетичні алгоритми виконуються наступним чином: На першому кроці відбору є випадкова початкова популяція і оцінювання її властивості. В подальшому, в кожній ітерації з популяції вибираються батьки. Батьки породжуюють нащадків, які додаються до популяції. Для всіх новостворених особин існує близка до нуля правдоподібність, що вони мають мутації, тобто що мають невеликі зміни частини їх генетичного матеріалу. В подальшому, деякі особини будуть усунені з популяції, згідно визначеного критерію селекції з метою приведення кількості популяції до її початкової кількості. Одна ітерація алгоритму приймається як генетація. Оператори, які визначають спосіб створення нащадків і процес мутації, називаються як оператори схрещування і оператори мутації. Мутація і схрещування мають різні ролі в генетичних алгоритмах. Мутація потрібна, щоб визначити нові потенційні можливості і допомогти алгоритму уникнути попадання у локальний мінімум. Схрещування повинно визначити середні властивості ціл...